from networkx import bfs_tree
from numpy.ma.core import max


class TreeThumbprintGenerator:
        
    def weighNodes(self, tree, node, parent):     
        total = 1 
        children = [neighbor for neighbor in tree.neighbors(node) if neighbor != parent]
        for neighbor in children:
                    total += self.weighNodes(tree, neighbor, node)
        tree.node[node]["weight"] = total
        return total    
    
    def shift(self,graph, currentNodeId):
        neighbors  = graph.neighbors(currentNodeId)
        for neighborId in neighbors:     
            if graph.node[neighborId]["weight"] > (graph.number_of_nodes() / 2.0):
                graph.node[currentNodeId]["weight"] -= graph.node[neighborId]["weight"]
                graph.node[neighborId]["weight"] += graph.node[currentNodeId]["weight"]
                return self.shift(graph, neighborId)
            elif graph.node[neighborId]["weight"] == (graph.number_of_nodes() / 2.0):
                return [currentNodeId, neighborId]
        return [currentNodeId]
        
    def findRoots(self,graph):        
        degrees = graph.degree().values()
        maximum=max(degrees)
        count=degrees.count(maximum)
        if count == 1:
            return [degrees.index(maximum)]
        else:
            self.weighNodes(graph, 0, -1)
            return self.shift(graph, 0)
        
    
    def treeCode(self,tree, node): 
        neighbors = tree.neighbors(node)
        subtreeLabels=[]
        for neighbor in neighbors:
            subtreeLabels.append(self.treeCode(tree, neighbor))
            
        sortedSubtreeLabels=sorted(subtreeLabels)
        
        if len(neighbors) == 0: 
            return str(len(neighbors))
        else: 
            return str(len(neighbors)) + "," + ",".join(sortedSubtreeLabels)
            
    
    def generateThumbprint(self,graph):
        roots = self.findRoots(graph)
        codes=[]
        for root in roots:
            tree=bfs_tree(graph,root)
            code=self.treeCode(tree, root)
            codes.append(code)
        codes=sorted(codes)
        return codes[0]
